#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 1010, M = 10010;
int h[N], e[M], ne[M], w[M], idx;
//状态0表示的是求最下，状态1表示求的是次小
int cnt[N][2];  // cnt[i][0]表示当前到达节点是i，且求的是0状态下的所有路径中最短路径的边数
int dist[N][2]; // dist[i][0]表示当前到达节点是i，且求的是0状态下的最短路径的值
bool st[N][2];  //与上面同理
int n, m, S, T; // S表示起点，T表示终点

struct node
{                           //小根堆，重载大于号
    int id, type, distance; //分别是编号，状态，和当前点到起点的最小或次小距离
    bool operator>(const node &a) const
    { //从大到小排序
        return distance > a.distance;
    }
};

void add(int a, int b, int c)
{
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dijkstra()
{

    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);

    priority_queue<node, vector<node>, greater<node>> heap;
    dist[S][0] = 0;
    cnt[S][0] = 1;
    heap.push({S, 0, 0});

    while (heap.size())
    {

        node t = heap.top();
        heap.pop();

        int ver = t.id, type = t.type, distance = t.distance;
        if (st[ver][type])
            continue;
        st[ver][type] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];

            //先考虑最短的情况(大于、等于)
            if (dist[j][0] > dist[ver][type] + w[i])
            {
                // dist[j][0]成为次小,先要赋值给dist[j][]中次小的状态
                dist[j][1] = dist[j][0];
                cnt[j][1] = cnt[j][0];
                heap.push({j, 1, dist[j][1]}); //发生改变就要入队

                dist[j][0] = dist[ver][type] + w[i];
                cnt[j][0] = cnt[ver][type]; //直接转移
                heap.push({j, 0, dist[j][0]});
            }
            else if (dist[j][0] == dist[ver][type] + w[i])
            {

                cnt[j][0] += cnt[ver][type]; //从t经过的最短路，在j上经过的时候也是最短路

                //轮到枚举次小
            }
            else if (dist[j][1] > dist[ver][type] + w[i])
            {

                dist[j][1] = dist[ver][type] + w[i];
                cnt[j][1] = cnt[ver][type];
                heap.push({j, 1, dist[j][1]});
            }
            else if (dist[j][1] == dist[ver][type] + w[i])
            {
                cnt[j][1] += cnt[ver][type]; //从t经过的最短路，在j上经过的时候也是最短路
            }
        }
    }
    int res = cnt[T][0];
    //最后还要特判以下最小和次小的路径之间是否相差1符合要求
    if (dist[T][0] + 1 == dist[T][1])
        res += cnt[T][1];
    return res;
}

int main()
{
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    int t;
    cin >> t;
    while (t--)
    {
        memset(h, -1, sizeof h);
        cin >> n >> m;
        for (int i = 0; i < m; ++i)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        scanf("%d%d", &S, &T);
        cout << dijkstra() << endl;
    }
    return 0;
}

